/*************************************************************************
	> File Name: 004.扩展欧几里得算法.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 日  8/22 22:09:07 2021
 ************************************************************************/

#include <stdio.h>

//求解a * x + b * y = gcd(a, b)的最小整数解

int ex_gcd(int a, int b, int *x, int *y) {
    if (!b) { //k_0项
        *x = 1;
        *y = 0;
        return a;
    }

    int xx, yy, ret = ex_gcd(b, a % b, &xx, &yy); //k_i项
    //k_i的前一项k_(i-1)项
    *x = yy;
    *y = xx - a / b * yy;
    return ret;
}

int main() {
    int a, b, x, y; //x，y为传出参数
    while (~scanf("%d%d", &a, &b)) {
        printf("gcd(%d, %d) = %d\n", a, b, ex_gcd(a, b, &x, &y));
        printf("%d * %d + %d * %d = %d\n", a, x, b, y, a * x + b * y);
    }

    return 0;
}

/*测试结果：
9 27
gcd(9, 27) = 9
9 * 1 + 27 * 0 = 9
3 4
gcd(3, 4) = 1
3 * -1 + 4 * 1 = 1
5 25
gcd(5, 25) = 5
5 * 1 + 25 * 0 = 5
7 9
gcd(7, 9) = 1
7 * 4 + 9 * -3 = 1 
*/
